package main

import (
	"fmt"
	"math"
)

/*
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
*/

func main() {
	nums := []int{1, 2}
	fmt.Println(maxProfit(nums))
}

//func maxProfit(prices []int) int {
//	minPrice := math.MaxInt16
//	max := 0
//	for i := 0; i < len(prices); i++ {
//		if  prices[i] < minPrice{
//			minPrice = prices[i]
//		}else if prices[i]-minPrice > max {
//			max = prices[i]-minPrice
//		}
//	}
//	return max
//}

/*
动态规划 前i天的最大收益 = max{前i-1天的最大收益，第i天的价格-前i-1天中的最小价格}
*/

func maxProfit(prices []int) int {
	minPrice := math.MaxInt16
	maxNums := make([]int, len(prices))
	for i := 1; i < len(prices); i++ {
		if prices[i-1] < minPrice {
			minPrice = prices[i-1]
		}
		// 当 prices[i] - minPrice > maxNums[i-1]的这一天就该卖了
		maxNums[i] = int(math.Max(float64(maxNums[i-1]), float64(prices[i]-minPrice)))
	}
	return maxNums[len(maxNums)-1]
}
